public class Solution528 {
    int[] w;
    double[] percent=new double[10001];

    public Solution528(int[] w) {
        this.w=w;
        int count=0;
        for (int i : w) {
            count=count+i;
        }
        int sum=0;
        for(int i=0;i<w.length;i++){
           percent[i]=(double)sum/count;
           sum=sum+w[i];
        }
        percent[w.length]=1;
    }

    public int pickIndex() {
        double z= Math.random();
        int l=0,r=w.length-1,mid=(l+r)/2;
        while (true){
            if (z<percent[mid]){
                r=mid-1;
            }else if (z>percent[mid+1]){
                l=mid+1;
            }else{
                break;
            }
            mid=(l+r)/2;
        }
        return mid;
    }

    public static void main(String[] args) {
        System.out.println(new Solution528(new int[]{1,3}).pickIndex());
    }
}
